package letcode.oneQuestionPerDay._202004._21;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Description: 统计【优美子数组】
 * @Date: 2020/4/21
 * @Author: 许群星
 */
public class StaticsPefectArrays {
    public static void main(String[] args) {
        int[] arr={1,1,2,1,1};
        int k=3;
        int[] arr1={2,4,6};
        int k1=1;
        int[] arr2={2,2,2,1,2,2,1,2,2,2};
        int k2=2;
        int[] arr3={91473,45388,24720,35841,29648,77363,86290,58032,53752,87188,34428,85343,19801,73201};
        int k3=4;

        System.out.println(numberOfSubarrays(arr3,k3));

    }
    //提供方法
    public static int numberOfSubarrays(int[] nums, int k) {
        int n=nums.length;
        int[] oddNumber=new int[n];

        //得到奇数的个数 和奇数对应的位置信息
        int count=0;
        for (int i = 0; i < n; i++) {
            if (nums[i]%2==1){
                oddNumber[i]=i;
                count++;
            }
        }
        Arrays.sort(oddNumber);
        int[] odd=Arrays.copyOfRange(oddNumber,n-count,n);

        //如果奇数个数为0，直接返回0
        if (count==0)
            return 0;

        int left=odd[0];
        int right=n-odd[count-1]-1;
        int  ans=1+left+right+left*right;
        //k大于奇数个数，默认取所有的
        if (k>=count)
            return ans;
        else{
            //k小于count的话,首先加上差额
            ans+=(count-k);
            //其次加上遍历取的k个数到k+1个数的偶数信息
            int first=0,second=k-1;
            while (second<count){
                if (first>=1&&second<count-1){
                    ans+=odd[second+1]-odd[second]-1+odd[first]-odd[first-1]-1;
                    first++;
                    second++;
                }else if (second==count-1){
                    ans+=odd[first]-odd[first-1]-1;
                    break;
                }else {
                    ans+=odd[second+1]-odd[second]-1;
                    first++;
                    second++;
                }
            }
            return ans;
        }
    }
}
/*
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
 

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */